package tree.structure.treetype;
import tree.structure.TreeNode;

/**
 * @user 26233
 * @create 2020-04-06 21:53:47
 * @description
 **/

public class AVLTree<T extends Comparable> {

    public TreeNodeComparable init(T[] t){
        if(t.length < 1)
            return null;
        TreeNodeComparable root = new TreeNodeComparable(t[0]);
        for (int i = 1; i < t.length; i++){
            //insert(root, t[i]);
            root = insertNoneRecursion(root, t[i]);
            //updateHeight(root);
        }

        return root;
    }

    public TreeNodeComparable insert(TreeNodeComparable<T> root, T t){
        if(t.compareTo(root.getValue()) >= 0){
            if (root.right != null){
                root = (TreeNodeComparable<T>) root.right;
                insert(root, t);
            }else{
                TreeNodeComparable newNode = new TreeNodeComparable(t);
                root.right = newNode;
                newNode.parent = root;
            }
        }else{
            if(root.left != null){
                root = (TreeNodeComparable<T>) root.left;
                insert(root, t);
            }else{
                TreeNodeComparable newNode = new TreeNodeComparable(t);
                root.left = newNode;
                newNode.parent = root;
            }
        }
        return root;
    }

    // 非递归插入元素
    public TreeNodeComparable insertNoneRecursion(TreeNodeComparable<T> root, T t){
        TreeNodeComparable preNode = root;
        while(root != null){
            preNode = root;
            if(t.compareTo(root.getValue()) >= 0){
                root = (TreeNodeComparable) root.right;
                if(root == null){
                    TreeNodeComparable newNode = new TreeNodeComparable(t);
                    preNode.right = newNode;
                    newNode.parent = preNode;
                    break;
                    //return;
                }
            }else{
                root = (TreeNodeComparable) root.left;
                if(root == null){
                    TreeNodeComparable newNode = new TreeNodeComparable(t);
                    preNode.left = newNode;
                    newNode.parent = preNode;
                    break;
                    //return;
                }
            }
        }
        return treeBalanceCheck(preNode);
    }

//    1、如果删除节点left和right都为null，则指向该节点的指针置null,检查父节点的平衡性
//    2、如果删除节点只有左子或右子树，则原来指向删除节点的指针指向删除节点的子树（左或右子树），平衡性不受影响
//    3、如果删除节点存在左右子树，则将删除节点的【后继】替换到删除节点，从后继节点开始检查平衡性
    public TreeNodeComparable delete(TreeNodeComparable root, T t){
        TreeNode currentNode = search(root, t);
        if(currentNode == null){
            return root;
        }
        // 1、2两种情况
        if(currentNode.right == null || currentNode.left == null){
            TreeNode parent = currentNode.parent;
            // 存在子树时，删除不影响平衡性
            if (currentNode.parent.left == currentNode){
                if(currentNode.left == null){
                    currentNode.parent.left = currentNode.right;
                }else{
                    currentNode.parent.left = currentNode.left;
                }
            }else{
                if(currentNode.left == null){
                    currentNode.parent.right = currentNode.right;
                }else{
                    currentNode.parent.right = currentNode.left;
                }
            }

            // 不存在子树时可能影响平衡
            if(currentNode.right == null && currentNode.left == null){
                root = treeBalanceCheck((TreeNodeComparable) parent);
            }
        }
        // 第3种情况
        if(currentNode.left != null && currentNode.right != null){
            TreeNode successor = successor(root, t);
            // 从后继开始检查平衡性
            TreeNode parent = successor.parent;
            if(successor.parent.left == successor){
                successor.parent.left = successor.right;// 后继至多只有一个右子女（BST情况下）
            }else{
                successor.parent.right = successor.right;
            }
            currentNode.setValue(successor.getValue());

            root = treeBalanceCheck((TreeNodeComparable) parent);
        }
        return root;
    }

    public TreeNode search(TreeNode root, T t){
        while(root != null) {
            if (root.getValue().equals(t)) {
                return root;
            }
            if (t.compareTo(root.getValue()) > 0) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        return null;
    }

    // 二叉搜索树最小值
    public TreeNode minNode(TreeNode root){
        while(root.left != null){
            root = root.left;
        }
        return root;
    }

    // 查找二叉树的中序遍历的后继
    public TreeNode successor(TreeNode root, T t){
        TreeNode currentNode = search(root, t);
        if(currentNode == null)
            return null;

        if(currentNode.right != null){
            return minNode(currentNode.right);
        }

        // 这里针对普通BST的后继查找，比如删除根节点左子树下处于最右端的节点时，它的后继是根节点
        // 在AVL中，不会使用到
        // 后继不是父节点（当前为左节点）就是根节点（当前为右节点）
        TreeNode parent = currentNode.parent;
        while(parent != null && parent.right == currentNode){
            currentNode = currentNode.parent;
            parent = currentNode.parent;
        }
        return parent;
    }


    /**
     * insert:
     *      从[插入节点]开始，一直上升到根节点，对不满足平衡因子条件的节点进行调整
     *      即直接检查插入节点后的父节点即可
     * delete:
     *      根据情况调整
     */
    public TreeNodeComparable treeBalanceCheck(TreeNodeComparable root){
        int diffHeightLR;
        TreeNodeComparable resultRoot = root;
        while(root != null){
            diffHeightLR = diffHeightLR(root);
            if(diffHeightLR > 1){
                // LL
                root = LLRotate(root);
            }else if(diffHeightLR < -1){
                // RR
                root = RRRotate(root);
            }
            resultRoot = root;
            root = (TreeNodeComparable) root.parent;
        }

        return resultRoot;
    }

    public int diffHeightLR(TreeNodeComparable root){
        if(root.left == null && root.right == null){
            return 0;
        }
        if(root.left == null && root.right != null){
            return - treeHeight((TreeNodeComparable) root.right) - 1;
        }
        if(root.left != null && root.right == null){
            return treeHeight((TreeNodeComparable) root.left) + 1;
        }
        if(root.left != null && root.right != null){
            return treeHeight((TreeNodeComparable) root.left) - treeHeight((TreeNodeComparable) root.right);
        }
        return 0;
    }

    public TreeNodeComparable LLRotate(TreeNodeComparable root){
         // LR
         if(diffHeightLR((TreeNodeComparable) root.left) < 0){
            root.left = LRRotate((TreeNodeComparable) root.left);
         }

        TreeNodeComparable tempNode = (TreeNodeComparable) root.left;
        tempNode.parent = root.parent;
        root.left = tempNode.right;
        if(root.parent != null){
            if(root.parent.left == root)
                root.parent.left = tempNode;
            else
                root.parent.right = tempNode;
        }
        root.parent = tempNode;
        //tempNode.parent = root;
        tempNode.right = root;
        return tempNode;
    }

    public TreeNodeComparable RRRotate(TreeNodeComparable root){
        // RL
        if(diffHeightLR((TreeNodeComparable) root.right) > 0){
            root.right = RLRotate((TreeNodeComparable) root.right);
        }
        // RR
        TreeNodeComparable tempNode = (TreeNodeComparable) root.right;
        tempNode.parent = root.parent;
        root.right = tempNode.left;
        if(root.parent != null){
            if(root.parent.right == root)
                root.parent.right = tempNode;
            else
                root.parent.left = tempNode;
        }
        root.parent = tempNode;
        tempNode.left = root;
        return tempNode;
    }

    public TreeNodeComparable RLRotate(TreeNodeComparable root){
        TreeNodeComparable parent = (TreeNodeComparable) root.parent;
        root.parent.right = root.left;
        root.left.right = root;
        root.parent = root.left;
        root.left = null;
        root.parent.parent = parent;
        return (TreeNodeComparable) root.parent;
    }

    public TreeNodeComparable LRRotate(TreeNodeComparable root){
        TreeNodeComparable parent = (TreeNodeComparable) root.parent;
        root.parent.left = root.right;
        root.right.left = root;
        root.parent = root.right;
        root.right = null;
        root.parent.parent = parent;
        return (TreeNodeComparable) root.parent;
    }

    public int treeHeight(TreeNodeComparable root){
        if(root.right == null && root.left == null){
            return 0;
        }
        if(root.left == null && root.right !=null ){
            return treeHeight((TreeNodeComparable) root.right) + 1;
        }
        if(root.right == null && root.left != null){
            return treeHeight((TreeNodeComparable) root.left) + 1;
        }
        return Math.max(treeHeight((TreeNodeComparable) root.left) + 1, treeHeight((TreeNodeComparable) root.right) + 1);
    }

    public static int treeHeight2(TreeNodeComparable root){
        if(root == null){
            return 0;
        }
        return Math.max(treeHeight2((TreeNodeComparable) root.left) + 1, treeHeight2((TreeNodeComparable) root.right) + 1);
    }

    // 更新整棵树的所有结点的高度　
    public int updateHeight(TreeNodeComparable root){
        if(root.left != null && root.right != null){
            root.height = Math.max(updateHeight((TreeNodeComparable) root.left), updateHeight((TreeNodeComparable) root.right)) + 1;
        }
        if(root.left == null && root.right != null){
            root.height = updateHeight((TreeNodeComparable) root.right) + 1;
        }
        if(root.left != null && root.right == null){
            root.height = updateHeight((TreeNodeComparable) root.left) + 1;
        }
        return root.height;
    }

    public static void main(String[] args){

        Integer[] data = new Integer[]{7, 1, 5, 3, 6, 9, 2, 10, 11, 12, 13, 14, 15};
        // LL
        //Integer[] data = new Integer[]{5, 4, 3};
        //Integer[] data = new Integer[]{20, 21, 15, 8, 5};
        // 标准LL
        //Integer[] data = new Integer[]{20, 21, 16, 17, 15, 8};

        // LL->LR
        //Integer[] data = new Integer[]{20, 21, 15, 8, 13};
        //Integer[] data = new Integer[]{20, 21, 15, 8, 16, 17};

        // RR
        //Integer[] data = new Integer[]{5, 6, 7};
        //Integer[] data = new Integer[]{10, 9, 11, 12, 13};
        //Integer[] data = new Integer[]{10, 9, 15, 14, 19, 18};

        // RL->RR
        //Integer[] data = new Integer[]{10, 9, 15, 14, 19, 13};
        //Integer[] data = new Integer[]{20, 21, 10, 17, 15};
        TreeNodeComparable root = new AVLTree<Integer>().init(data);

        System.out.println("tree Height: " + AVLTree.treeHeight2(root));

        // delete avl element
        root = new AVLTree<Integer>().delete(root, 11);
        root = new AVLTree<Integer>().delete(root, 15);
        root = new AVLTree<Integer>().delete(root, 13);
        root = new AVLTree<Integer>().delete(root, 12);
        root = new AVLTree<Integer>().delete(root, 5);

        //System.out.println("root height: " + new AVLTree<>().treeHeight(root));
        //System.out.println("root height: " + new AVLTree<>().treeHeight((TreeNodeComparable) root.left));

        //List<TreeNode> levelOderList = new TreeUtil<Integer>().levelOrder(root);

        //new AVLTree<Integer>().updateHeight(root);

        System.out.println("end");

    }

}
